1. Field of the Invention
The present invention relates to an automatic image processing and pattern recognition method, and more particularly, to a method for locating a decipherable pattern in an input image captured by an arbitrary image acquisition device, such as a camera, a scanner, CIS (contact image sensor), and various types of hand-held devices such as a mobile phone, a personal digital assistant (PDA), and/or the like.
2. Description of the Prior Art
The decipherable pattern in the present invention refers to a pattern containing a plurality of lines at intervals, such as barcodes and biological signature of human fingerprints, which are widely used nowadays in various industries. Take barcodes as an example, a barcode is a typical decipherable pattern which is just a different way of encoding numbers and letters by using a combination of bars and spaces of varying widths. In business, the correct use of barcodes can reduce inefficiencies and improve a company's productivity. Logistics, manufacturing, healthcare, retail, security, etc. all have symbologies unique to their industry and aren't interchangeable.
Barcodes come in many styles and forms. Most of us are familiar with the ones seen in grocery or retail stores, but there are many others that are used as standards in various industries. No matter how differently they may look, any existing commercial barcode reader devices involve only two major functions, one is for barcode locating and the other for barcode decoding. For the locating function, there are three basic types of barcode readers—fixed, portable batch, and portable wireless. Fixed readers (hand held or mounted) remain attached to their host computer or terminal, and transmit one data item at a time as the barcode is scanned. Although many decoding algorithms have been developed, most existing hand-held barcode readers, especially in the case of 2-D barcode, must rely on the user to manually maneuver the reader device to the barcode region roughly centered at an auxiliary light point emitted from the reader, that is, correct decoding is possible only when the user can complete the maneuvering task in order to successfully target the barcode. This inefficiency problem could easily become worse if the hand-held reader device is used to process large number of articles with decipherable patterns, and it becomes even complicated the case where parcels vary greatly in size and shape. This limitation of manual locating must be removed in order to realize automation and efficiency improvement.
With the great increase in resolution of digital cameras that come as standard equipment on various types of portable devices, it is possible that users can locate and decode the decipherable patterns by taking pictures without using the auxiliary light point provided by the portable devices. Through the high resolution (e.g., SXGA, 1280×1024) image sensors on the portable device, an user can easily acquire a picture that encompass the decipherable pattern by merely moving the portable device close to a decipherable pattern and taking the picture. Generally, the decipherable pattern thus obtained would be in random location and orientation within the taken pictures. Furthermore, it is not rare to see that barcodes are located close to graphic and other text elements, all of which add significant “noise” to the barcode locating. An exemplary method of locating a barcode within a picture taken via a high-resolution imaging system is described in U.S. Pat. No. 6,729,544, entitled “Fast barcode search”, which divides the captured image into a plurality of tiles and then scans each tile so as to detect a pattern of stripes associated with the barcode in at least one of the tiles, the pattern of stripes is analyzed later so as to determine an angle of orientation of the barcode. However, because the method is applied under original image resolution and the original image needs to be entirely scanned (i.e., a region of interest needs to be pre-defined) to achieve barcode locating, computation load will raise rapidly as the image resolution increases. Thus, the search algorithms that perform computation on the original image plane are not practical, if one considers using a cost-saving and light-weight portable device to handle the task of finding decipherable patterns with arbitrary locations in a high resolution image. Furthermore, presence of other graphic and other text elements in the input image and partial corruption of the decipherable patterns per se also raise the possibility of erroneous search.
In view of the foregoing, a need exists in the art to develop a simple and fast locating algorithm capable of automatically locating a decipherable pattern in a very large, noisy image within the tight time constraints of a cost-saving portable device.